#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#include "biTree.h"

void midPrint(BiTree T){
	if(T){
		midPrint(T->lchild);
		printf("%d ",T->key);
		midPrint(T->rchild);
	}
}

int insertBiSearchTree(BiTree *T,int key){
	BiTreeNode *p = NULL;
	BiTreeNode *q = NULL;
	if(*T){
		p = *T;
		while(p){
			q = p;
			if(p->key<key){
				p = p->rchild;
			}else if(p->key>key){
				p = p->lchild;
			}else{
				return ERR;
			}
		}
		p = (BiTreeNode *)malloc(sizeof(BiTreeNode));
		p->key = key;
		p->lchild = NULL;
		p->rchild = NULL;
		if(q->key<key){
			q->rchild = p;
		}else if(q->key>key){
			q->lchild = p;
		}
		
	}else{
		p = (BiTreeNode *)malloc(sizeof(BiTreeNode));
		p->key = key;
		p->lchild = NULL;
		p->rchild = NULL;
		*T = p;
	}
	return OK;
}

int searchBiSearchTree(BiTree p,BiTree *s,int key){
	if(p){
		BiTreeNode *q = p;
		while(q){
			if(q->key>key){
				q = q->lchild;
			}else if(q->key<key){
				q = q->rchild;
			}else{
				*s = q;
				return OK;
			} 
		}
	}
	return ERR;
}

int deleteBiSearchTree(BiTree p,int key){
	if(p){
		BiTreeNode *q = p;
		BiTreeNode *s = NULL;
		while(q){
			if(q->key>key){
				s = q;
				q = q->lchild;
			}else if(q->key<key){
				s = q;
				q = q->rchild;
			}else{
				break;
			} 
		}
		if(q==NULL){
			return ERR;
		}else{
			if(q->rchild==NULL){
				if(s!=NULL){
					if(s->lchild==q){
						s->lchild = q->lchild;
					}else if(s->rchild==q){
						s->rchild = q->lchild;
					}
				}
				free(q);
			}else{
				if(q->lchild==NULL){
					if(s->lchild==q){
						s->lchild = q->rchild;
					}else if(s->rchild==q){
						s->rchild = q->rchild;
					}
				}else{
					BiTreeNode *k = q->lchild;
					s = k;
					while(k->rchild){
						s = k;
						k = k->rchild;
					}
					if(s->rchild){
						q->key = s->rchild->key;
						q = s->rchild;
						s->rchild=q->lchild;
					}else{
						q->lchild = s->lchild;
						q = s;
					}
					free(q);
				}
			}
			return OK;
		}
	}
	return ERR;
}


int main(){
	srand((unsigned)time(NULL));
	int key=0;
	int i=0;
	int size = 10;
	int range = 100;
	BiTree tree = NULL;
	
	//insert test
    for(i=0;i<size;i++){
        key = rand()%range;
		insertBiSearchTree(&tree,key);
    }
	midPrint(tree);
	printf("\n");
	
	printf("search test==\n");
	//search test
	int arr[10];
	int j=0;
	int flag = 0;
	for(i=0;i<size;i++){
		key = rand()%range;
		flag = 0;
		for(j=0;j<i;j++){
			if(arr[j]==key){
				flag = 1;
				break;
			}
		}
		if(flag){
			i--;
		}else{
			arr[i]=key;
		}
	}
	tree = NULL;
	for(i=0;i<size;i++){
		insertBiSearchTree(&tree,arr[i]);
    }
	printf("arr: [");
	for(i=0;i<size;i++){
		printf("%d ",arr[i]);
	}
	printf("]\n");
	midPrint(tree);
	printf("\n");
	key = arr[5];
	BiTree s = NULL;
	searchBiSearchTree(tree,&s,key);
	printf("result key: %d\n",s->key);
	key = arr[5]+1;
	if(!searchBiSearchTree(tree,&s,key)){
		printf("result key: %d\n",s->key);
	}else{
		printf("not found key: %d\n",key);
	}
	midPrint(tree);
	printf("\n");
	
	printf("delelte test==\n");
	//delete test
	key = arr[5];
	if(!deleteBiSearchTree(tree,key)){
		printf("success\n");
	}
	key = arr[5]-1;
	if(!deleteBiSearchTree(tree,key)){
		printf("success\n");
	}else{
		printf("not found key: %d\n",key);
	}
	
	midPrint(tree);
	printf("\n");
	
	return 0;
}